class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if word1 == word2:
            return 0
        if len(word1) == 0 or len(word2) == 0:
            return max(len(word1), len(word2))
        res_list = [[0 for i in word1] for j in word2]
        # print(res_list)
        res_list[0][0] = int(word1[0] != word2[0])
        flag = True
        for i in range(1, len(word1)):
            if word1[i] == word2[0] and flag:
                res_list[0][i] = res_list[0][i-1]
                flag = False
            else:
                res_list[0][i] = res_list[0][i - 1] + 1
        flag = True
        for j in range(1, len(word2)):
            if word1[0] == word2[j] and flag:
                res_list[j][0] = res_list[j-1][0]
                flag = False
            else:
                res_list[j][0] = res_list[j - 1][0] + 1
        # print(res_list)
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                res_list[j][i] = min(res_list[j-1][i] + 1, res_list[j][i-1] + 1,
                                     res_list[j-1][i-1] + int(word1[i] != word2[j]))
        return res_list[-1][-1]




a = Solution()
print(a.minDistance(word1="horse", word2="ros"))
print(a.minDistance(word1="intention", word2="execution"))
print(a.minDistance(word1="sea", word2="eat"))